This invention relates generally to the encoding of data for transmission and storage, more particularly the invention relates to the encoding of Reed-Solomon (RS) codes.
The trend towards higher densities and data rates in magnetic data recording has required error control coding and modulation techniques. Error detection and correction coding can use a polynomial with binary coefficients to represent a sequence of binary bits and with a plurality of check bits determined by a coding process which requires that every code word be divisible by a preselected polynomial with zero remainder. A plurality of cyclic codes can be interleaved to form a cyclic code for further error reduction. Further, the binary base field can be extended to a finite field of 2.sup.m elements, known as a Galois field GF (2.sup.m) in which all elements are represented by m-bit binary symbols.
The Reed-Solomon (RS) code is based on an extension of the concepts of cyclic codes in an extended binary field GF (2.sup.M). All processing of these polynomials is done using sum and product operations defined in the extension field GF (2.sup.m). In this system, the generator G(z), the information sequence B(z), the remainder C(z), and the code word W(z) are all polynomials whose coefficients are elements in GF(2.sup.m) in the form of m-bit bytes.
An (n,k) Reed-Solomon (RS) code over the finite field FG(2.sup.m) has k message symbols and r=n-k redundant check symbols, where each symbol is m bits wide and n=r+k total code length in symbols. The check symbols C.sub.r-1, C.sub.r-2 . . . , C.sub.1, C.sub.0 are computed from the message symbols M.sub.k-1, M.sub.k-2 . . . , M.sub.1, M.sub.0 using the formula EQU C(z)=M(z)z.sup.r modulo G(z)
where C(z)=C.sub.r-1 z.sup.r-1 +C.sub.r-2 Z.sup.r-2 + . . . +C.sub.1 z+C.sub.0 is the check polynomial, M(z)=M.sub.k-1 z.sup.k-2 + . . . +M.sub.1 z+M.sub.0 is the message polynomial and G(z)=z.sup.r +G.sub.r-1r-1 +G.sub.r-2 z.sup.r-2 + . . . +G.sub.1 z+G.sub.0 is the generator polynomial of the RS code. C(z) is the remainder when M(z)z.sup.r is divided by G(z).
The conventional parallel implementation of a RS encoder is shown in FIG. 1 in which a message and the content of a register are summed and applied through a MUX 10 to a plurality of multipliers 12 which multiply the sum by coefficients, G.sub.1, with the products added to contents of registers 14 in adders 16 and then stored in other registers 14.
In this parallel approach, a message symbol is input every clock cycle, and r finite field multiplications (by the r constant coefficients, G.sub.1, of the generator polynomial) and r finite field additions are performed every clock cycle. The message select signal is high when message symbols are being input and low when the redundant check symbols are being output. The other signals in FIG. 1 are all m bits wide where m is the number of bits per symbol. In this approach, r constant finite field multipliers 12, r finite field adders 16, and r symbol registers 14 are needed.
Various other RS encoder architectures has been proposed, depending on the required throughput data rate of the application. Using the Cauchy representation of the RS generator matrix, Seroussi has proposed a systolic implementation which is particularly suitable for very high speed implementation in "A Systolic Reed-Solomon Encoder", IEEE Trans. on Information Theory Vol. IT-37, No. 4, p. 1217-1220, July 1991. For lower throughput applications, Berlekamp discloses in "Bit-Serial Reed-Solomon Encoders", IEEE Trans. on Information Theory, Vol. IT-28, No. 6, p. 869-874, November 1982, a bit-serial architecture by exploiting the properties of dual basis representation of finite field elements. Berlekamp's bit-serial architecture assumes the availability of a bit clock whose rate is m times the symbol rate. In comparison to the parallel approach, the complexity of the r constant finite field multipliers and r finite field adders are reduced by a ratio of roughly m:1. Yet another approach is the microcoded sequencer architecture disclosed in U.S. Pat. No. 4,162,480. In this architecture, the throughput data rate is usually limited by the number of memory accesses, and the speed of the memory access cycle.
The present invention is directed to the efficient encoding of Reed-Solomon codes using serial encoding and discrete time delay lines.